package com.nanbei.divideandconqure;

import java.util.Arrays;

/**
 * @ClassDescription:  (分治)给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/12 10:37
 */
public class LongestSubstringWithAtLeastKRepeatingCharacters { // LeetCode395
    public static void main(String[] args) {
        int i = longestSubstring("aaabbccc", 3);
        System.out.println(i);
    }

    public static int longestSubstring(String s, int k) {
        // 子串落选情况
        if (s.length() < k) {
            return 0;
        }


        char[] chars = s.toCharArray();
        int[] charArr = new int[26];
        for (char aChar : chars) {
            charArr[aChar-'a']++;
        }
        System.out.println(Arrays.toString(charArr));

        for (int i = 0; i < charArr.length; i++) {
            // 该字符出现的次数小于K
            if (charArr[i] < k && charArr[i] !=0){
                // 在字符串中需找到该字符然后进行切割将不满足条件的切割掉
                for (int j = 0; j < s.length(); j++) {
                    char c = s.charAt(j);
                    // 找到不满足条件的字符后继续判断该字符的下一个字符是否和该字符是同一字符（如果是则一并切除）
                    if (c == i+'a'){
                        int end = j+1;
                        int start = j;
                        while (end < s.length()){
                            if (s.charAt(end) == i+'a'){
                                end++;
                            }else{
                                j = end;
                                break;
                            }
                        }

                        // 如果字符中存在不满足条件的字符，则进行切割，在将字串进行递归相同的操作，最后返回最长的字符
                        String substring = s.substring(0, start);
                        String substring1 = s.substring(end);
                        return Math.max(longestSubstring(substring,k),longestSubstring(substring1,k));
                    }
                }
            }
        }
        // 字符串中字符出现的次数全部满足条件则直接返回字符的长度
        return s.length();
    }
}
